//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
// 
//
// 示例 2： 
//
// 
//输入：height = [4,2,0,3,2,5]
//输出：9
// 
//
// 
//
// 提示： 
//
// 
// n == height.length 
// 1 <= n <= 2 * 10⁴ 
// 0 <= height[i] <= 10⁵ 
// 
// 👍 3163 👎 0


package leetcode.editor.cn;

//接雨水

import leetcode.editor.cn.level.困难;

public class P42_接雨水 implements 困难 {
    public static void main(String[] args) {
        Solution solution = new P42_接雨水().new Solution();
        System.out.println(solution.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int trap(int[] height) {
//            return violenceRainWater(height);
            return markRainWater(height);
        }

        /**
         * 思路：
         * 维护左右最大的柱子和下标
         *
         * @param height
         * @return
         */
        private int markRainWater(int[] height) {
            int res = 0;
            int rightIndex = -1, leftIndex = -1;
            int maxRight = Integer.MIN_VALUE, maxLeft = Integer.MIN_VALUE;
            for (int i = 0; i < height.length; i++) {
                if (!(i >= leftIndex && i <= rightIndex)) {
                    maxRight = Integer.MIN_VALUE;
                    maxLeft = Integer.MIN_VALUE;
                    for (int left = i; left >= 0; left--) {
                        if (height[left] >= maxLeft) {
                            leftIndex = i;
                            maxLeft = height[left];
                        }
                    }
                    for (int right = i; right < height.length; right++) {
                        if (height[right] >= maxRight) {
                            rightIndex = i;
                            maxRight = height[right];
                        }
                    }
                }
                res += Math.min(maxLeft, maxRight) - height[i];
            }

            return res;
        }

        /**
         * 暴力思路：
         * 遍历每个柱子 找到每个柱子左边和右边的最大值，计算差值
         *
         * @param height
         * @return
         */
        private int violenceRainWater(int[] height) {
            int res = 0;

            for (int i = 0; i < height.length; i++) {
                int maxLeft = height[i], maxRight = height[i];
                for (int left = i; left >= 0; left--) {
                    maxLeft = Math.max(maxLeft, height[left]);
                }
                for (int right = i; right < height.length; right++) {
                    maxRight = Math.max(maxRight, height[right]);
                }
                res += Math.min(maxLeft, maxRight) - height[i];

            }

            return res;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}